The approaches described in this section could be pursued, but are not necessarily approaches that have been previously conceived or pursued. Therefore, unless otherwise indicated herein, the approaches described in this section are not prior art to the claims in this application and are not admitted to be prior art by inclusion in this section.
In computer networks such as the Internet, packets of data are sent from a source to a destination via a network of elements including links (communication paths such as telephone or optical lines) and nodes (for example, routers directing the packet along one or more of a plurality of links connected to it) according to one of various routing protocols.
One class of routing protocol is the link state protocol. The link state protocol relies on a routing algorithm resident at each node. Each node on the network advertises, throughout the network, links to neighboring nodes and provides a cost associated with each link, which can be based on any appropriate metric such as link bandwidth or delay and is typically expressed as an integer value. A link may have an asymmetric cost, that is, the cost in the direction AB along a link may be different from the cost in a direction BA. Based on the advertised information in the form of a link state packet (LSP) each node constructs a link state database (LSDB), which is a map of the entire network topology, and from that constructs generally a single optimum route to each available node based on an appropriate algorithm such as, for example, a shortest path first (SPF) algorithm. As a result a “spanning tree” is constructed, rooted at the node and showing an optimum path including intermediate nodes to each available destination node. The results of the SPF are stored in a routing information base (RIB) and based on these results a forwarding information base (FIB) or forwarding table is updated to control forwarding of packets appropriately. When there is a network change an LSP representing the change is flooded through the network by each node adjacent the change, each node receiving the LSP sending it to each adjacent node.
As a result, when a data packet for a destination node arrives at a node the node identifies the optimum route to that destination and forwards the packet via the correct interface to the next node (“NEXT_HOP”) along that route. The next node repeats this step and so forth.
Such protocols can support both unicast, i.e. single point (source) to single point (destination) data traffic and multicast traffic. Multicast traffic comprises point to multipoint traffic (P2 MP) and multipoint to multipoint traffic (MP2 MP). For example IP (internet protocol) multicast is well known to the skilled reader and is described in document “Internet Protocol Multicast” which is available at the time of writing on the file “IP multi.htm” in the directory “univercd/cc/td/doc/cisintwk/ito_doc” of the domain cisco.com on the World Wide Web.
Multicast allows data packets to be forwarded to multiple destinations (or “receivers”) without unnecessary duplication, reducing the amount of data traffic accordingly. All hosts wishing to become a receiver for a multicast group perform a “join” operation to join the multicast group. A multicast tree such as a shortest path tree is then created providing routes to all receivers in the group. The multicast group in a P2 MP group is denoted (S,G) where S is the address of the source or broadcasting host and G is an IP multicast address taken from a reserved address space. As a result routers receiving a packet from the source S to the multicast address G send the packet down each interface providing a next hop along the route to any receiver on the tree.
In the case of MP2 MP multicasts, a shared group is denoted (*,G) allowing multiple sources to send to multiple receivers. The multicast tree is constructed as a shared tree including a shared root or rendez-vous point (RP) which can be determined in any appropriate manner, for example using a “Steiner tree” as will be familiar to the skilled reader. All of the sources register into and send multicast data for the group to the RP which then sends the data down the shared tree to all receivers. In either case the multicast tree is dynamically modified as hosts join, and pruned as hosts leave. For example, if a path changes, a router will send a prune up the old path immediately cutting off the supply of packets, and simultaneously switch the input interface to the new path, sending a join up that path.
During forwarding of multicast data at a router, when a packet is received at the router with a multicast address as destination address, the router consults the multicast forwarding table and sends the packet to the correct next hop via the corresponding interface. As a result, even if the path from the next hop subsequently branches to multiple receivers, only a single multicast packet needs to be sent to the next hop. If, at the router, more than one next hop is required, that is to say the multicast tree branches at the router, then the packet is copied and sent on each relevant output interface.
In order to avoid looping each router ensures that data is only sent downstream away from the source and towards the receiver as upstream-directed traffic would loop back, which is impermissible in multicast. In order to achieve this the router carries out a reverse path forwarding (RPF) check to ensure that the incoming packet has arrived on the appropriate input interface. If the check fails then the packet is dropped. The router uses the unicast forwarding table to identify the appropriate upstream and downstream interfaces in the tree as part of the RPF and only forwards packets arriving from the upstream direction.
Multicast methods which make use of existing forwarding information in this manner belong to the family of “protocol independent multicast” (PIM) methods as they are independent of the specific routing protocol adopted at each router.
Referring to FIG. 1, which is an illustrative network diagram showing implementation of multicast, a network is shown designated generally 100. The network includes nodes A, B, C, D, E, reference numbers 102, 104, 106, 108, 110 respectively. Node B is joined to nodes A, C, D and E via links 112, 114, 116 and 118 respectively. In addition the network includes a multicast group with source S, reference numeral 120 connected to node A via a path 122 which may include additional intermediate routers. The multicast group further comprises receivers X and Y, reference numerals 124, 126 respectively joined to nodes D and E respectively by paths 128, 130. Accordingly when nodes X and Y join the multicast group G with source S they send join messages “JOIN(S,G)” via respective paths 128, 130 which are passed on by nodes D and E towards node S and then via node B and finally node A along the path 122. As a result each node, acting in the multicast router, updates its forwarding table appropriately.
In addition to IP multicast, schemes such as multi-protocol label switching (MPLS) multicast are well known. MPLS is a protocol that is well known to the skilled reader and which is described in document “Multi Protocol Label Switching Architecture” which is available at the time of writing on the file “rfc3031.txt” in the directory “rfc” of the domain “ietf.org” on the World Wide Web. According to MPLS, a complete path for a source-destination pair is established, and values required for forwarding a packet between adjacent routers in the path together with headers or “labels” are pre-pended to the packet. The labels are used to direct the packet to the correct interface and next hop. The labels precede the IP or other header allowing smaller outer headers.
The path for the source-destination pair, termed a Label Switched Path (LSP) can be established according to various different approaches. One such approach is Label Distribution Protocol (LDP) in which each router in the path sends its label to the next hop router on the path as determined from its IP routing table. Alternatively Resource Reservation Protocol (RSVP-TE) can be invoked in which case, for example, a network administrator can engineer a path, providing strict source routing. In the case of MPLS multicast, therefore, for example, a multicast tree is constructed for example from a P2 MP or MP2 MP LSP.
In the case of failure of network components such as a node or link multicast traffic can be affected until the network converges on the new topology. A solution to this problem is known from MPLS multicast and is described in “Multicast Fast Reroute” which is available at the time of writing on the file “mpls” in the directory “˜mngroup/projects” of the domain cs.virginia.edu on the World Wide Web. According to the solution presented therein backup LSPs are precomputed either manually or using an algorithm minimizing the number of routers disconnected from the routing tree for a link failure.
However effective and rapid solutions are required for both link and node protection in, and also embracing IP multicast schemes. Furthermore, during convergence, the interruption to multicast traffic can be proportional to the number of multicast trees on the network. In particular there is a need to switch between old and new input interfaces in the case where the topology change affects which router acts as the preceding router before a given multicast router. In existing systems, when the prune and join messages are sent to update the forwarding decision, during transition across the network, traffic arriving at the old input interface is lost and so there is a delay in receiving traffic until all traffic is coming in on the new input interface.